package com.sympsel.Optimal_Algorithm_OA;

import org.junit.Test;

public class SimulationAlgorithm {

    public String modifyString(String s) {
        char[] str = s.toCharArray();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            if (str[i] == '?') {
                for (char c = 'a'; c <= 'z'; c++) {
                    if ((i == 0 || str[i - 1] != c) && (i == n - 1 || str[i + 1] != c)) {
                        str[i] = c;
                        break;
                    }
                }
            }
        }
        return new String(str);
    }

    @Test
    public void test1() {
        String s = "??yw?ipkj?";
        System.out.println(modifyString(s));
    }

    //
//    public String convert(String s, int numRows) {
//        int len = s.length();
//        int gap = (numRows - 1) << 1;
//        if (len == 1 || gap == 0) {
//            return s;
//        }
//        char[] str = new char[len];
//        int k = 0;
//        Queue<Integer> queue = new LinkedList<>();
//        for (int i = 0; i < len; i += gap) {
//            queue.offer(i);
//        }
//        while (!queue.isEmpty()) {
//            int index = queue.poll();
//            if (k == len) {
//                break;
//            }
//            str[k++] = s.charAt(index);
//            if (index % gap == 0) {
//                if (index > 0 && (index - 2) % gap != 0) {
//                    queue.offer(index - 1);
//                }
//                if (index < len - 1) {
//                    queue.offer(index + 1);
//                }
//
//            } else {
//                if (index > 0 && index % gap > (gap >> 1) + 1) {
//                    queue.offer(index - 1);
//                }
//                if (index < len - 1 && index % gap < (gap >> 1)) {
//                    queue.offer(index + 1);
//                }
//            }
//            if ((len - 1) % gap > (gap >> 1) && (len - 1) % gap - (gap >> 1) == (index + 1) % gap) {
//                queue.offer(len - 1);
//            }
//        }
//        return String.valueOf(str);
//    }

    public String convert(String s, int numRows) {
        int gap = (numRows - 1) << 1;
        int len = s.length();
        if (gap == 0 || len < 3) {
            return s;
        }
        char[] str = new char[len];
        int k = 0;
        for (int i = 0; i < len; i += gap) {
            str[k++] = s.charAt(i);
        }

        for (int i = 1; i < numRows - 1; i++) {
            for (int j = i, m = gap - i; j < len || m < len; j += gap, m += gap) {
                if (j < len) {
                    str[k++] = s.charAt(j);
                }
                if (m < len) {
                    str[k++] = s.charAt(m);
                }
            }
        }

        for (int i = numRows - 1; i < len; i += gap) {
            str[k++] = s.charAt(i);
        }
        return String.valueOf(str);
    }

    @Test
    public void test2() {
        System.out.println(convert("ABCD", 3));
        System.out.println(convert("ABCD", 2));
        System.out.println(convert("PAYPALISHIRING", 3));
        System.out.println(convert("ABC", 2));
    }

    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        String prep = countAndSay(n - 1);
        int len = prep.length();
        int left = 0, cnt = 0;
        StringBuilder sb = new StringBuilder();
        for (int right = 0; right < len; right++) {
            char leftChar = prep.charAt(left);
            if (prep.charAt(right) == leftChar) {
                cnt++;
            } else {
                sb.append(cnt).append(leftChar);
                left = right;
                cnt = 1;
            }
        }
        return sb.append(cnt).append(prep.charAt(left)).toString();
    }

    public String countAndSay2(int n) {
        if (n == 1) {
            return "1";
        }
        String ret = "1";
        for (int i = 1; i < n; i++) {
            int len = ret.length();
            int left = 0, cnt = 0;
            StringBuilder sb = new StringBuilder();
            for (int right = 0; right < len; right++) {
                char leftChar = ret.charAt(left);
                if (leftChar == ret.charAt(right)) {
                    cnt++;
                } else {
                    sb.append(cnt).append(leftChar);
                    cnt = 1;
                    left = right;
                }
            }
            ret = sb.append(cnt).append(ret.charAt(left)).toString();
        }
        return ret;
    } // 1 11 21 1211 111221 312211

    @Test
    public void test3() {
        System.out.println(countAndSay2(6));
        System.out.println(countAndSay(6));
    }

    public int minNumberOfFrogs(String croakOfFrogs) {
        int len = croakOfFrogs.length();
        if (len < 5) {
            return -1;
        }
        int[] arr = new int[6];
        for (int i = 0; i < len; i++) {
            reflect(arr, croakOfFrogs.charAt(i));
            if (arr[5] == -1) {
                return -1;
            }
        }
        return arr[4];
    }

    private void reflect(int[] arr, char ch) {
        switch (ch) {
            case 'c':
                if (arr[4] > 0) {
                    arr[4]--;
                }
                arr[0]++;
                break;
            case 'r':
                if (arr[0] > 0) {
                    arr[0]--;
                    arr[1]++;
                } else {
                    arr[5] = -1;
                }
                break;
            case 'o':
                if (arr[1] > 0) {
                    arr[1]--;
                    arr[2]++;
                } else {
                    arr[5] = -1;
                }
                break;
            case 'a':
                if (arr[2] > 0) {
                    arr[2]--;
                    arr[3]++;
                } else {
                    arr[5] = -1;
                }
                break;
            case 'k':
                if (arr[3] > 0) {
                    arr[3]--;
                    arr[4]++;
                } else {
                    arr[5] = -1;
                }
                break;
        }
    }

    @Test
    public void test4() {
        System.out.println(minNumberOfFrogs("croakcroak"));
        System.out.println(minNumberOfFrogs("crcoakroak"));
        System.out.println(minNumberOfFrogs("croakcrook"));
    }
}
